1. Field of the Invention
The present invention relates to a method and apparatus for quickly and efficiently rendering graphic images on a computer graphics display device. More particularly, the present invention relates to a method and apparatus for rendering trimmed NURBS primitives on a computer graphics display device.
2. Art Background
In the past, computer graphic systems required extensive display and computer resources. The amount of computation time required to render images was substantial. Images of any complexity required powerful computers to process hours in order to generate the image. Today, technology has greatly improved. The rendering of three dimensional ("3D") objects is no longer a process reserved for high-powered mainframe computers. The rendering of complex graphic objects is now realized on smaller, less powerful computers.
Furthermore, graphics processes have become more sophisticated. In particular the utilization of sophisticated graphic primitives are now prevalent. However the utility of the sophisticated graphic primitives are measured in part by the speed a computer system can render the primitive on a display device. An example of such a primitive is a trimmed NURBS. A trimmed NURBS is a non-uniform rational B-spline surface with trimming loops which define the relevant portions of the surface.
The generation of the graphic image represented by a trimmed NURBS is quite complex and time consuming, outweighing many of the benefits gained by using the trimmed NURBS primitive to define a graphic object. The rendering problem is compounded considering the dynamic and interactive nature of computer graphics today.
Techniques have been developed to render curved surface, such as NURBS, directly from the curved surface primitives which define the surface. See, for example, Jeffrey Lane, Loren Carpenter, Turner Whitted, James Blinn, "Scan Line Methods For Displaying Parametrically Defined Surfaces", Communications of the ACM, 23(1), January, 1980; and Sheue-Ling Lien, Michael Shantz and Vaughan Pratt, "Adaptive Forward Differencing For Rendering Curves and Surfaces", Computer Graphics, 21(4), pp. 111-117July, 1987. However these techniques are not general in application and apply to a very restricted class of NURBS. Furthermore, trimming is also not handled in a general manner.
In the article, Alyn Rockwood, Kurt Heaton and Tom Davis, "Real-Time Rendering of Trimmed Surfaces", Proceedings of the ACM, SIGGRAPH '89, Computer Graphics, Volume 23, Number 3, July 1989, pp. 107-116a technique to break down a complex trimmed NURBS surface into triangles before rendering is described. This technique however, repeatedly performs complex, time consuming process steps for each rendered view of the image.